/*
* Valentine Gladstein
* SOLAR ID 108731583
* Homework #3
* CSE214
* Recitation 03-Phil Ammirato
* Grading TA: Yanjie Li
*/

import java.io.*;
import java.util.*;

public class CityList {  

    //The CityList class stores a list of cities and stores information about which cities are connected by flights.

    private final int MAX_CITIES = 20;

    private String[] cityNames; 
    private boolean[] visited;
    private int manyItems;
    private MyLinkedList[] adjacentCities;

/**
 * The default constructor. Initiates all data structures.
 * 
 */

    public CityList() {
	cityNames = new String[MAX_CITIES];
	visited = new boolean[MAX_CITIES];
	adjacentCities = new MyLinkedList[MAX_CITIES];
    }

/**
 * A private helper method used internally to find the index at
 * which a city is stored.
 * @param String city : the city whose index is to be found
 * @return the index at which @param is found, -1 if @param is not found
 */

    private int getIndexOf(String city) {
	for(int i = 0; i < manyItems; i++) {
	    if (cityNames[i].equals(city)) {
		return i;
	    }
	}
	return -1;
    }

/**
 * Adds a new city to the cityNames array
 * @param String city : the city to be added
 */

    public void addCity(String city) throws AddCityException{
	if (manyItems >= MAX_CITIES)
	    throw new AddCityException("cityNames list is full");
	if (getIndexOf(city) != -1)
	    throw new AddCityException("item is already in the list");
	cityNames[manyItems] = city;
	visited[manyItems] = false;
	manyItems++;
    }

/**
 * Adds a new entry to the adjacentCities list to represent a new flight.
 * @param String originCity : the flight's origin
 * @param String destCity   : the flight's destination
 */

    public void addPath(String originCity, String destCity) throws NoSuchCityException {
	int pos = getIndexOf(originCity);
	if (pos == -1)
	    throw new NoSuchCityException(originCity + " is not found in cityNames");
	if (adjacentCities[pos] == null) {
	    adjacentCities[pos] = new MyLinkedList();
	    adjacentCities[pos].add(originCity);
	}
	adjacentCities[pos].add(destCity);
    }

/**
 * Marks a selected city as visited in the visited array.
 * @param String city : the city to be marked as visited
 */

    public void markAsVisited(String city) throws NoSuchCityException {
	int pos = getIndexOf(city);
	if (pos == -1)
	    throw new NoSuchCityException(city + " not found.");
	visited[pos] = true;
    }

/**
 * Marks all cities in the list as unvisited
 *
 */

    public void unvisitAll() {
	for (int i = 0; i < manyItems; i++) {
	    visited[i] = false;
	}
    }

/**
 * Gets an unvisited city which is adjacent to the @param
 * @param String city : the city to which an adjacent city is to be found
 * @return String     : An unvisited city adjacent to @param, null if none exists
 */

    public String getNextUnvisitedCity(String city) throws NoSuchCityException {
	int pos = getIndexOf(city);
	if (pos == -1)
	    throw new NoSuchCityException(city + " was not found.");
	try {
	    adjacentCities[pos].cur = adjacentCities[pos].head;
	}catch(NullPointerException e){return null;}
	while (adjacentCities[pos].cur.hasNext()) {
	    adjacentCities[pos].cur = adjacentCities[pos].cur.getNext();
	    int index = getIndexOf(adjacentCities[pos].cur.getData());
	    if (visited[index] == false)
		return cityNames[index];
	}
	throw new NoSuchCityException("No unvisited adjacent cities found.");
    }
    
/**
 * Determines whether there is a series of connecting flights between two cities.
 * @param String originCity : the origin city to be tested
 * @param String destCity   : the destination city to be tested
 * @return boolean          : true if there is a series of connecting 
 *                            flight between the two @param cities. 
 *                            False otherwise.
 */

    public boolean isPath(String originCity, String destCity) throws NoSuchCityException{
	if (getIndexOf(originCity) == -1)
	    throw new NoSuchCityException(originCity + " was not found.");
	if (getIndexOf(destCity) == -1)
	    throw new NoSuchCityException(destCity + " was not found.");
	Stack<String> s = new Stack<String>();
	unvisitAll();
	s.push(originCity);
	try {
	    markAsVisited(originCity);
	    String topCity = s.peek();
	    while (!s.empty() && destCity != topCity) {
		String nextCity = getNextUnvisitedCity(topCity);
		if (nextCity == null)
		    s.pop();
		else {
		    s.push(nextCity);
		    markAsVisited(nextCity);
		}
		if (!s.empty())
		    topCity = s.peek();
	    }
	}catch(NoSuchCityException e){} //exception does not need to be explicitely handled because the validity of cities is tested at the start of the method
	    return (!s.empty());
    }
    
}
